<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <meta http-equiv="X-UA-Compatible" content="ie=edge" />
  <title>深度优先遍历和广度优先遍历</title>
  <style>
  </style>
</head>

<body>
  <div class="parent">
    <div class="child-1">
      <div class="child-1-1">
        <div class="child-1-1-1">a</div>
      </div>
      <div class="child-1-2">
        <div class="child-1-2-1">b</div>
      </div>
      <div class="child-1-3">c</div>
    </div>
    <div class="child-2">
      <div class="child-2-1">d</div>
      <div class="child-2-2">e</div>
    </div>
    <div class="child-3">
      <div class="child-3-1">f</div>
    </div>
  </div>
  <script>
    let deepFirstSearch1 = (node, nodeList = []) => {
      if (node !== null) {
        nodeList.push(node)
        const children = node.children
        for (let i = 0; i < children.length; i++) {
          deepFirstSearch1(children[i], nodeList)
        }
      }
      return nodeList
    }
    let deepFirstSearch2 = node => {
      let nodeList = []
      if (node !== null) {
        nodeList.push(node)
        const children = node.children
        for (let i = 0; i < children.length; i++) {
          nodeList = nodeList.concat(deepFirstSearch2(children[i]))
        }
      }
      return nodeList
    }
    let deepFirstSearch3 = node => {
      // 栈stack先进后出
      const stack = []
      const nodeList = []
      if (node) {
        stack.push(node)
        while (stack.length) {
          const item = stack.pop()
          nodeList.push(item)
          const children = item.children
          for (let i = children.length - 1; i >= 0; i--) {
            stack.push(children[i])
          }
        }
      }
      return nodeList
    }
    let widthFirstSearch = node => {
      // 队列queue先进先出
      const queue = []
      const nodeList = []
      if (node) {
        queue.push(node)
        while (queue.length) {
          const item = queue.shift()
          nodeList.push(item)
          const children = item.children
          for (let i = 0; i < children.length; i++) {
            queue.push(children[i])
          }
        }
      }
      return nodeList
    }
    const parent = document.querySelector('.parent')
    console.log(deepFirstSearch1(parent))
    console.log(deepFirstSearch2(parent))
    console.log(deepFirstSearch3(parent))
    console.log(widthFirstSearch(parent))

  </script>
</body>

</html>
